package month1;

import java.util.*;

public class OrangesRotting994_06 {
    public static void main(String[] args) {
        System.out.println(orangesRotting(new int[][]{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}));
    }

    /**
     * 多源BFS
     * @param grid
     * @return
     */
    static int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
        Map<Integer, Integer> cnt = new HashMap<>();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    cnt.put(i * n + j, 0);
                    q.offer(i * n + j);
                }
            }
        }
        int ret = 0;
        while (!q.isEmpty()) {
            int index = q.poll();
            int r = index / n, c = index % n;
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];
                if (nr >= 0 && nr < m && nc < n && nc >= 0 && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int newIndex = nr * n + nc;
                    cnt.put(newIndex, cnt.getOrDefault(index, 0) + 1);
                    ret = cnt.get(newIndex);
                    q.offer(newIndex);
                }
            }
        }
        for (int[] row : grid) {
            for (int val : row) {
                if (val == 1) {
                    return -1;
                }
            }
        }
        return ret;
    }
}

